package org.example.BinaryTree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class Sequence_traversal_of_binary_trees {
    public static List<List<Integer>> resList = new ArrayList<List<Integer>>();
    public static void main(String[] args) {
        //二叉树的层序遍历

        //给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(4);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(1);
        TreeNode root = new TreeNode(0);
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right =  node4;
        node2.left = node5;
        //checkFun01(root,0);
        //root=null;
        checkFun02(root);
        System.out.print("[ ");
        for (List<Integer> list :resList){
            System.out.print("[ ");
            for (Integer i : list) {
                System.out.print(i+" ");
            }
            System.out.print("] ");
        }
        System.out.print("]");
    }
    //递归法
    public static void checkFun01(TreeNode root,int deep) {
        if (root==null) return;
        //当递归返回时，即将函数在栈中运行时，会将deep的值-1，即还回本来的值
        deep++;
        if (resList.size()<deep){
            ArrayList<Integer> item = new ArrayList<>();
            resList.add(item);
        }
        resList.get(deep-1).add(root.val);
        //先创建数组将左子树的值添加，再添加右子树
        checkFun01(root.left,deep);
        checkFun01(root.right,deep);
    }
    //迭代法
    public static void checkFun02(TreeNode root){
        if (root==null) return;
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.add(root);
        while(!deque.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            int len = deque.size();
            while(len>0){
                TreeNode node = deque.poll();
                list.add(node.val);
                if (node.left!=null) deque.add(node.left);
                if (node.right!=null) deque.add(node.right);
                len--;
            }
            resList.add(list);
        }
    }


}
